package acwing._1_1AlgorithmBasic;
/**
 * @Project : AlgorithmLearning
 * @Package : ACWing._1_1AlgorithmBasic.AlgorithmTemplate
 * @File : _3_3ShortestPath.java
 * @Author : WangRuoyu
 * @Date : 2023/3/29 14:39
 */

import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class _3_3ShortestPath {
    static int n;
    static int[][] p;


    public static int[] dijkstra1(int x) {
        int[] dist = new int[n + 1];
        boolean[] st = new boolean[n + 1];
        Arrays.fill(dist, (int) 1e9);
        dist[x] = 0;

        for (int i = 1; i < n; ++i) {
            int index = -1;
            for (int j = 1; j <= n; ++j) {
                if (!st[j] && (index == -1 || (dist[index] > dist[j]))) {
                    index = j;
                }
            }
            st[index] = true;
            for (int j = 1; j <= n; ++j) {
                dist[j] = Math.min(dist[j], dist[index] + p[index][j]);
            }
        }
        return dist;
    }

    static int[] h;
    static int[] w;
    static int[] e;
    static int[] next;
    static int idx = 0;

    static int[] dijkstra2(int x) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[0] != o2[0] ? o1[0] - o2[0] : o1[1] - o2[1]);
        boolean[] st = new boolean[n + 1];
        int[] res = new int[n + 1];
        Arrays.fill(res, 0x3f3f3f3f);
        res[x] = 0;
        pq.add(new int[]{0, x});
        while (!pq.isEmpty()) {
            int[] point = pq.poll();
            int dis = point[0];
            int t = point[1];
            if (st[t]) continue;
            for (int i = h[t]; i != -1; i = next[i]) {
                int j = e[i];
                if (res[j] > dis + w[i]) {
                    res[j] = dis + w[i];
                    pq.add(new int[]{res[j], j});
                }
            }
            st[t] = true;
        }

        return res;
    }

    static int k;
    static int m;
    static int[][] edge;
    static int[] last;

    static int[] bellmanFord(int x) {
        int[] res = new int[n + 1];
        Arrays.fill(res, 0x3f3f3f3f);
        res[x] = 0;
        for (int i = 0; i < k; i++) {
            System.arraycopy(res, 0, last, 0, n + 1);
            for (int j = 0; j < m; j++) {
                int a = edge[j][0];
                int b = edge[j][1];
                int w = edge[j][2];
                res[b] = Math.min(res[b], last[a] + w);
            }
        }
        return res;
    }

    // spfa求最短路径
    static int[] spfa(int x) {
        int[] res = new int[n + 1];
        boolean[] st = new boolean[n + 1];

        Arrays.fill(res, 0x3f3f3f3f);
        res[x] = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(x);
        st[x] = true;

        while (!q.isEmpty()) {
            int point = q.poll();
            st[point] = false;

            for (int i = h[point]; i != -1; i = next[i]) {
                int j = e[i];
                if (res[j] > res[point] + w[i]) {
                    res[j] = res[point] + w[i];
                    if (!st[j]) {
                        q.add(j);
                        st[j] = true;
                    }
                }
            }
        }

        return res;
    }

    // spfa判断是否存在负环
    static boolean spfa() {
        int[] res = new int[n + 1];
        boolean[] st = new boolean[n + 1];
        int[] cnt = new int[n + 1];

        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= n; ++i) {
            q.add(i);
            st[i] = true;
        }

        while (!q.isEmpty()) {
            int point = q.poll();
            st[point] = false;

            for (int i = h[point]; i != -1; i = next[i]) {
                int j = e[i];
                if (res[j] > res[point] + w[i]) {
                    res[j] = res[point] + w[i];
                    cnt[j] = cnt[point] + 1;
                    if (cnt[j] >= n) {
                        return true;
                    }
                    if (!st[j]) {
                        q.add(j);
                        st[j] = true;
                    }
                }
            }
        }

        return false;
    }

    // 弗洛伊德算法求最短路
    static int[][] dis;
    static void floyd() {
        for (int l = 1; l <= n; ++l) {
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= n; ++j) {
                    dis[i][j] = Math.min(dis[i][j], dis[i][l] + dis[l][j]);
                }
            }
        }
    }
}
